#include"Graph.h"
template<class solving_problem>
void DepthFirstSearch(const Graph& graph, solving_problem& task) {
    std::vector<bool> visited(graph.GetNumberOfVertices(), false);
    for(int vertex = 0; vertex < graph.GetNumberOfVertices(); vertex++) {
	if(!visited[vertex]){
	    DFSImplementation(graph, task, visited, vertex);
        }
    }
}

template <class solving_problem>
void DFSImplementation(const Graph& graph, solving_problem& task, std::vector<bool>& visited, int start_vertex) {
    std::stack<int> stack;
    stack.push(start_vertex);
    while (!stack.empty()){
        int vertex = stack.top();
        if (!visited[vertex]){
            visited[vertex] = true;
            task.EnterVertex(vertex);
	    std::set<int> incident_list = graph.GetIncidentList(vertex);
	    for (std::set<int>::iterator index = incident_list.begin(); index != incident_list.end(); index++) {
	        int incident_vertex = *index;
	        task.ProcessEdge(vertex, incident_vertex);
	        if (!visited[incident_vertex]) {
	            stack.push(incident_vertex);
		}
            }
	}
	else{
	    task.LeaveVertex(vertex);
	    stack.pop();
	}
    }
}

enum DFSStage{
    NOT_VISITED,
    PROCESSING,
    LEFT
};


class TopologicalSort{
public:
    TopologicalSort(int vertices_number) : state(vertices_number, NOT_VISITED) {}
    void EnterVertex(int vertex){
        state[vertex] = PROCESSING;
    }
    void ProcessEdge(int begin_vertex, int end_vertex){
        try{
            if(state[end_vertex] == PROCESSING){
                throw std::logic_error("ERROR: Circle found in given Graph");
            }
        } catch (const std::exception& ex){
            throw std::logic_error(std::string(ex.what()));
        };
    }
    void LeaveVertex(int vertex){
        if(state[vertex] == PROCESSING){
            SortedGraph.push_back(vertex);
            state[vertex] = LEFT;
        }
        
    }
    std::vector<int> GetSortedGraph(){
        std::vector <int> answer = SortedGraph;
	std::reverse(answer.begin(), answer.end());
	return answer;
    }
private:
    std::vector<int> SortedGraph;
    std::vector<DFSStage> state;
};


class TarjanAlgo{
public:
    TarjanAlgo(int vertices_number) : timer(0), time_in(vertices_number, 0), state(vertices_number, NOT_VISITED),
            root(vertices_number, true),component_for_vertex(vertices_number, -1), parent(vertices_number){}
    void EnterVertex(int vertex){
        state[vertex] = PROCESSING;
        stack.push(vertex);
        time_in[vertex] = timer;
        timer++;
    }
    void ProcessEdge(int from, int to){
        if(state[to] == NOT_VISITED){
            parent[to] = from;
        }
        if(state[to] == PROCESSING){
            if(from == to) return;
            time_in[from] = std::min(time_in[from], time_in[to]);
            root[from] = false;
        }
        if(state[to] == LEFT){
            if(component_for_vertex[to] == -1 && time_in[from] > time_in[to]){
                time_in[from] = time_in[to];
                root[from] = false;
            }
        }
    }
    void LeaveVertex(int vertex){
        if(state[vertex] == LEFT) return;
        state[vertex] = LEFT;
        if(time_in[parent[vertex]] > time_in[vertex]) {
	    time_in[parent[vertex]] = time_in[vertex];
	    root[parent[vertex]] = false;
	}

	if (root[vertex]) {
	    MakeComponent(vertex);    
	}
    }
    
    std::vector <std::set <int > > GetComponents() const {
        return components;
    }
    
    std::vector<int> GetComponentsForVertices(){
        return component_for_vertex;
    }
private:
    int timer;
    std::vector<int> time_in;
    std::vector<DFSStage> state;
    std::vector<std::set <int > > components;
    std::stack <int> stack;
    std::vector <int> parent;
    std::vector <bool> root;
    std::vector<int> component_for_vertex;
    void MakeComponent(int vertex) {
        std::set<int> new_component;
	int current_vertex;
	while (true) {
	    current_vertex = stack.top();
	    stack.pop();
	    component_for_vertex[current_vertex] = components.size();
	    new_component.insert(current_vertex);
	    if (current_vertex == vertex) {	
		break;
	    }
    	}
	components.push_back(new_component);
    }
};

inline std::auto_ptr<Graph> MakeGraphCondensation(const Graph &graph, std::vector<std::set < int > > components){
    std::vector<int> component_for_vertex(graph.GetNumberOfVertices());
    for (int index = 0; index < components.size(); index++) {   
        for (std::set<int> ::iterator vertex = components[index].begin(); vertex != components[index].end(); vertex++) {
            component_for_vertex[*vertex] = index;
        }
    }
    std::set<edge> condensation_edges;
    for (int vertex = 0; vertex < graph.GetNumberOfVertices(); ++vertex) {
	std::set<int> incident_list = graph.GetIncidentList(vertex);
        std::set<int>::iterator iterator = incident_list.begin();
	for (int i = 0; i < incident_list.size(); ++i) {
	    int incident_vertex = *(iterator);
            iterator++;
	    if (component_for_vertex[incident_vertex] != component_for_vertex[vertex]){
                edge new_edge (component_for_vertex[vertex], component_for_vertex[incident_vertex]);
		condensation_edges.insert(new_edge);
            }
	}
    }
    std::vector<edge> edges(condensation_edges.begin(), condensation_edges.end());
    
    return MakeCompactGraph(components.size(), edges);
}